package backTrack;

import java.util.*;

public class Class40 {

    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<Integer>();
    boolean[] used;
    int sum = 0;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        used = new boolean[candidates.length];
        Arrays.fill(used, false);

        Arrays.sort(candidates);

        backTracking(candidates, target, 0);
        return result;
    }

    public void backTracking(int[] candidates, int target, int start) {
//        if (sum > target) {
//            return;
//        }
        if (sum == target) {
            result.add(new ArrayList<>(path));
            return;
        }
        int length = candidates.length;

        for (int i = start; i < length; i++) {

            if (sum + candidates[i] > target) {
                break;
            }
            if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {
                continue;
            }

            used[i] = true;
            path.add(candidates[i]);
            sum += candidates[i];
            System.out.print("=================================");
            Iterator<Integer> iterator = path.iterator();
            while (iterator.hasNext()){
                System.out.print(iterator.next()+" ");
            }
            System.out.println();
            backTracking(candidates, target, i+1);
            used[i] = false;
            sum -= candidates[i];
            path.removeLast();
        }

    }




    public static void main(String[] args) {
        Class40 class40 = new Class40();
        int arr[]={1, 1,1,2,3};
        System.out.println(class40.combinationSum2(arr, 5).toString());
    }


}
